package jp.ac.kobe_u.cs.cream;

import jp.ac.kobe_u.cs.cream.*;
import java.util.*;

public class IntDomain extends Domain {
    public static final int MIN_VALUE = 0xc0000001;
    public static final int MAX_VALUE = 0x3fffffff;
    public static IntDomain EMPTY = new IntDomain();
    public static IntDomain FULL = new IntDomain(MIN_VALUE, MAX_VALUE);
    private ArrayList intervals = new ArrayList();
    private int min;
    private int max;

    public IntDomain() {
    }

    public IntDomain(int val) {
	this(val, val);
    }

    public IntDomain(int mi, int ma) {
	mi = Math.max(mi, MIN_VALUE);
	ma = Math.min(ma, MAX_VALUE);
	if (mi <= ma) {
	    int interval[] = {mi, ma};
	    intervals.add(interval);
	    size = ma - mi + 1;
	    min = mi;
	    max = ma;
	}
    }

    private void updateSize() {
	size = 0;
	try {
	    for (int i = 0; i < intervals.size(); ++i) {
		int interval[] = (int[])intervals.get(i);
		size += interval[1] - interval[0] + 1;
	    }
	} catch (IndexOutOfBoundsException e) {}
    }

    private void updateMinMax() {
	if (size > 0) {
	    try {
		int interval[] = (int[])intervals.get(0);
		min = interval[0];
		interval = (int[])intervals.get(intervals.size() - 1);
		max = interval[1];
	    } catch (IndexOutOfBoundsException e) {}
	}
    }

    public boolean equals(Domain d0) {
	if (this == d0)
	    return true;
	if (! (d0 instanceof IntDomain))
	    return false;
	IntDomain d = (IntDomain)d0;
	if (intervals.size() != d.intervals.size())
	    return false;
	try {
	    for (int i = 0; i < intervals.size(); i++) {
		int i0[] = (int [])intervals.get(i);
		int i1[] = (int [])d.intervals.get(i);
		if (i0[0] != i1[0] || i0[1] != i1[1])
		    return false;
	    }
	} catch (IndexOutOfBoundsException e) {}
	return true;
    }

    public Object clone() {
	IntDomain d = new IntDomain();
	try {
	    for (int i = 0; i < intervals.size(); ++i) {
		d.intervals.add(((int[])intervals.get(i)).clone());
	    }
	} catch (IndexOutOfBoundsException e) {}
	d.size = size;
	d.min = min;
	d.max = max;
	return d;
    }

    public Iterator elements() {
	Iterator iter = new Iterator() {
		private int choice = min;

		public boolean hasNext() {
		    if (size == 0)
			return false;
		    while (choice <= max) {
			if (contains(choice))
			    return true;
			choice++;
		    }
		    return false;
		}
		
		public Object next() throws NoSuchElementException {
		    if (! hasNext())
			throw new NoSuchElementException();
		    IntDomain d = new IntDomain(choice);
		    choice++;
		    return d;
		}

		public void remove() throws UnsupportedOperationException {
		    throw new UnsupportedOperationException();
		}
	    };
	return iter;
    }

    public int min() throws NoSuchElementException {
	if (size == 0)
	    throw new NoSuchElementException();
	return min;
    }

    public int max() throws NoSuchElementException {
	if (size == 0)
	    throw new NoSuchElementException();
	return max;
    }

    public int value() throws NoSuchElementException {
	if (size != 1)
	    throw new NoSuchElementException();
	return min;
    }

    public Object element() throws NoSuchElementException {
	return new Integer(value());
    }

    private int indexOf(int elem) {
	if (elem < min || max < elem)
	    return -1;
	try {
	    for (int i = 0; i < intervals.size(); i++) {
		int interval[] = (int[])intervals.get(i);
		if (elem < interval[0])
		    return -1;
		if (elem <= interval[1])
		    return i;
	    }
	} catch (IndexOutOfBoundsException e) {}
	return -1;
    }

    private int indexOf(Object o) {
	if (! (o instanceof Number))
	    return -1;
	return indexOf(((Number)o).intValue());
    }

    public boolean contains(int elem) {
	return indexOf(elem) >= 0;
    }

    public boolean contains(Object o) {
	if (! (o instanceof Number))
	    return false;
	return contains(((Number)o).intValue());
    }

    public Domain insert(Object o) {
	System.out.println("insert: not implemented");
	return this;
    }

    public void remove(int elem) {
	int i = indexOf(elem);
	if (i < 0)
	    return;
	try {
	    int interval[] = (int[])intervals.get(i);
	    int lo = interval[0];
	    int hi = interval[1];
	    if (elem == lo && elem == hi) {
		intervals.remove(i);
	    } else if (elem == lo) {
		interval[0] = lo + 1;
	    } else if (elem == hi) {
		interval[1] = hi - 1;
	    } else {
		interval[0] = elem + 1;
		intervals.add(i, new int[] {lo, elem-1});
	    }
	    size--;
	    updateMinMax();
	} catch (IndexOutOfBoundsException e) {}
    }

    public void remove(Object o) {
	if (! (o instanceof Number))
	    return;
	remove(((Number)o).intValue());
    }

    public IntDomain delete(int elem) {
	if (! contains(elem))
	    return this;
	IntDomain d = (IntDomain)clone();
	d.remove(elem);
	return d;
    }

    public Domain delete(Object o) {
	if (! (o instanceof Number))
	    return this;
	return delete(((Number)o).intValue());
    }

    public IntDomain delete(int lo, int hi) {
	if (size == 0 || lo > hi || hi < min || max < lo)
	    return this;
	if (lo == hi)
	    return delete(lo);
	IntDomain d = new IntDomain();
	try {
	    for (int i = 0; i < intervals.size(); i++) {
		int interval[] = (int[])intervals.get(i);
		int mi = Math.max(lo, interval[0]);
		int ma = Math.min(hi, interval[1]);
		if (mi <= ma) {
		    if (interval[0] < mi) {
			int in[] = new int[2];
			in[0] = interval[0];
			in[1] = mi - 1;
			d.intervals.add(in);
		    }
		    if (ma < interval[1]) {
			int in[] = new int[2];
			in[0] = ma + 1;
			in[1] = interval[1];
			d.intervals.add(in);
		    }
		} else {
		    int in[] = new int[2];
		    in[0] = interval[0];
		    in[1] = interval[1];
		    d.intervals.add(in);
		}
	    }
	} catch (IndexOutOfBoundsException e) {}
	d.updateSize();
	d.updateMinMax();
	return d;
    }

    public Domain cap(Domain d) {
	if (! (d instanceof IntDomain))
	    return EMPTY;
	IntDomain new_d = new IntDomain();
	IntDomain d0 = this;
	IntDomain d1 = (IntDomain)d;
	try {
	    int interval[];
	    int min0, max0, min1, max1;
	    int i0 = 0;
	    int i1 = 0;
	    while (i0 < d0.intervals.size() && i1 < d1.intervals.size()) {
		interval = (int[])d0.intervals.get(i0);
		min0 = interval[0];
		max0 = interval[1];
		interval = (int[])d1.intervals.get(i1);
		min1 = interval[0];
		max1 = interval[1];
		if (max0 < min1) {
		    i0++;
		    continue;
		}
		if (max1 < min0) {
		    i1++;
		    continue;
		}
		interval = new int[2];
		interval[0] = Math.max(min0, min1);
		interval[1] = Math.min(max0, max1);
		new_d.intervals.add(interval);
		if (max0 <= max1)
		    i0++;
		if (max1 <= max0)
		    i1++;
	    }
	} catch (IndexOutOfBoundsException e) {}
	new_d.updateSize();
	new_d.updateMinMax();
	if (new_d.isEmpty())
	    return EMPTY;
	return new_d;
    }

    public Domain cup(Domain d) {
	System.out.println("cup: not implemented");
	return this;
    }

    public Domain difference(Domain d) {
	System.out.println("difference: not implemented");
	return this;
    }

    public IntDomain capInterval(int lo, int hi) {
	IntDomain d = this;
	if (MIN_VALUE < lo)
	    d = d.delete(MIN_VALUE, lo - 1);
	if (hi < MAX_VALUE)
	    d = d.delete(hi + 1, MAX_VALUE);
	return d;
    }

    private String toString(int x) {
	if (x == MIN_VALUE) {
	    return "min";
	} else if (x == MAX_VALUE) {
	    return "max";
	} else {
	    return Integer.toString(x);
	}
    }

    public String toString() {
	String s = "";
	String delim = "";
	try {
	    for (int i = 0; i < intervals.size(); i++) {
		int interval[] = (int[])intervals.get(i);
		s += delim + toString(interval[0]);
		if (interval[0] < interval[1]) {
		    s += "-" + toString(interval[1]);
		}
		delim = ",";
	    }
	} catch (IndexOutOfBoundsException e) {}
	if (size() == 1) {
	    return s;
	}
	return "{" + s + "}";
    }
}
